/**
 * @file heap_senya.h
 *
 * @brief heap implementation by senya
 *
 */

#ifndef _HEAP_SENYA_H_
#define _HEAP_SENYA_H_

#define tr(cont, it) for(typeof((cont).begin()) it = (cont).begin(); it != (cont).end(); ++it)

#include <cstdlib>
#include "../../api/heap.h"
#include "helpers.h"
#include "tlsf.h"
#include "options.h"
#include <map>
#include <set>
#include <sstream>
#include <iostream>
#include <fstream>


/** structure:
	[      ][prev][0][next][######]
	[######][1][next][sbit][      ]
	[######][1][next][######]

	begin of memory
	[1][next][ real block ]

	end of memory
	[?][next][1][zero]
*/
class heap_senya: public heap876 {
public:

	enum error {
		ok,        /// no errors
		no_memory, /// not enough memory
		bad_free,  /// trying free not allocated block
		//debug_not_used_block, /// alloc block and free it without use
		debug_dirty_block
	};

private:
	error last_error;

	typedef std::multimap< size_t, _block* >::iterator size_block_it;

	struct _tag_info {
		size_t sum;
		std::set<_block *> blocks;
	};

	_tlsf free_blocks;
	CRITICAL_SECTION glob_cs;
	byte *all_mem;
	_block *begin_block, *end_block;

	/**
		rb-tree overhead per node ~ 24 bytes (gcc, windows).
	*/
	static const size_t cell_power = 5;
	static const size_t cell_size = 1 << cell_power;

	/// occupied block overhead
	static const size_t oh_occ = sizeof(size_t);

	size_t occupancy;

	std::map< _block *, int > tags;
	std::map< int, _tag_info > tag_tree;
	std::set< _block * > alloc_blocks;

	int get_tag(_block *pbl) {
		if(tags.count(pbl) > 0)
			return tags[pbl];
		else
			return 0;
	}

	std::string block_info(_block *pbl) {
		std::ostringstream out;
		out << pbl << ": " << tagstr( get_tag(pbl) ) << (pbl->get_size() ? (pbl->free() ? "[free]" : "[alloc]") : "[]") << ", size:" << pbl->get_size();

		return out.str();
	}

	/** for inseting free block :
	**  set its next and prev_free fields;
	**  call insert_block - it will insert your
	**  block into the tree and IT WILL SET TO
	**  TRUE (your block)->next->prev_free and
	**  initialize addional data in free block
	**/
	void insert_block(_block *pbl) {
		assert(pbl >= begin_block);
		assert(pbl < end_block);

		pbl->next()->is_prev_free(1);
		pbl->next()->set_prev(pbl);
		free_blocks.insert(pbl);

		if(flag & alloc_debug) {
			fill_block_free(pbl);
		}

		LOG << "inserting block:" << std::endl;
		LOG << "  " << block_info(pbl) << std::endl;
	}

	size_t round_bytes(size_t bytes) {
		return (bytes + cell_size - 1) & ~(cell_size - 1);
	}

	///  @section alloc_debug functions

	void fill_block_alloc(_block *pbl) {
		memset(pbl->ptr(), 0xFFFFFFFF, pbl->get_user_size());
	}

	void fill_block_free(_block *pbl) {
		memset((void *)(pbl+1), 0xAAAAAAAA, (byte *)(pbl->next()) - (byte *)(pbl+1) - sizeof(_block *));
	}

	bool check_block_alloc(_block *pbl) {
		for(size_t *p = (size_t *)(pbl+1); p < (size_t *)(pbl->next()) - 1; ++p)
			if(*p != 0xAAAAAAAA)
				return false;

		return true;
	}

public:
	heap_senya( size_t total, alloc_flags flag);
	virtual ~heap_senya() {
		/// @todo check free_blocks and occupied_blocks
		if(sync) DeleteCriticalSection(&glob_cs);
		delete all_mem;
	}

	virtual void*	alloc( size_t sz, unsigned int tag = 0 );
	virtual void	free( void* ptr );
	virtual void	free_all( unsigned int tag );
	virtual size_t	get_occupancy() const;

	void memory_init();

	///  @section error functions
	error get_last_error() {
		return last_error;
	}

	bool all_right() {
		return last_error == ok;
	}


	///  @section logging functions
	int get_greedy_tag() {
		int m = 0;
		int tag = 0;
		tr(tag_tree, it)
			if(it->second.sum > m) {
				m = it->second.sum;
				tag = it->first;
			}

		return tag;
	}

	///  @section debugging functions

	void print_blocks() {
		LOG << "printing all blocks" << std::endl;
		for(_block *p = begin_block; p <= end_block; p = p->next()) {
			LOG << "  " << block_info(p) << std::endl;
		}
		LOG << "all blocks printed" << std::endl;
		LOG << std::endl;
	}

};

#endif //_HEAP_SENYA_H_
